package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.List;

public class PathSumII {

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(-2);
		root.right = new TreeNode(-3);
		
		root.left.left = new TreeNode(1);
		root.left.right = new TreeNode(3);
		
		root.right.left = new TreeNode(-2);
		
		root.left.left.left = new TreeNode(-1);
		
		PathSumII ps2 = new PathSumII();
		ps2.pathSum(root, 2);
		
	}
	public List<List<Integer>> pathSum(TreeNode root, int sum) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		List<Integer> l = new ArrayList<Integer>();
		helper(root, sum, 0, res, l);
		return res;
	}
	
	
	/** Do a preorder way
	 * 	{1,-2,-3,1,3,-2,#,-1}, 2
	 *           1
	 *      -2      -3 
	 *     1    3  -2 
	 *  -1   
	 * 
	 * path-> 1, -2, 3
	 */
	public void helper(TreeNode root, int sum, int cur, List<List<Integer>> res, List<Integer> l) {
		if (root == null) return;
		
		cur += root.val;
		if (root.left == null && root.right == null) {
			if (cur == sum) {
				l.add(root.val);
				res.add(new ArrayList<Integer>(l));
				l.remove(l.size() - 1);	
			}
			return;
		}
		
		l.add(root.val);		
		helper(root.left, sum, cur, res, l);
		helper(root.right, sum, cur, res, l);
		
		l.remove(l.size() - 1);
	}
}
